#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// 1652. 拆炸弹
class Solution1
{
public:
    vector<int> decrypt(vector<int>& code, int k) 
    {
        int n = code.size();
        vector<int> ret(n);
        if(k == 0) return ret;

        vector<int> sum(2 * n + 1);
        for(int i = 1; i <= 2 * n; ++i) sum[i] += sum[i - 1] + code[(i - 1) % n];
        for(int i = 1; i <= n; ++i)
        {
            if(k < 0)
                ret[i - 1] = sum[i + n - 1] - sum[i + n + k - 1];
            else
                ret[i - 1] = sum[i + k] - sum[i];
        }
        return ret;
    }
};

// 2139. 得到目标值的最少行动次数
class Solution2
{
public:
    int minMoves(int target, int maxDoubles) 
    {
        int ret = 0;
        while(target != 1)
        {
            if(maxDoubles == 0) 
            {
                ret += target - 1;
                break;
            }
            if(target % 2) 
            {
                --target;
                ++ret;
            }
            --maxDoubles;
            target /= 2;
            ++ret;
        }
        return ret;
    }
};

// 1052. 爱生气的书店老板
class Solution3
{
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) 
    {
        int n = customers.size(), ret = 0;
        for(int i = 0; i < n; ++i)
        {
            if(grumpy[i] == 0)
            {
                ret += customers[i];
                customers[i] = 0;
            }
        }

        int cur = 0, tmp = 0;
        for(int i = 0; i < n; ++i)
        {
            cur += customers[i];
            if(i >= minutes) cur -= customers[i - minutes];
            tmp = max(tmp, cur);
        }
        return ret + tmp;
    }
};

// 1962. 移除石子使总数最小
class Solution4
{
public:
    int minStoneSum(vector<int>& piles, int k) 
    {
        // 生成最大堆
        make_heap(piles.begin(), piles.end());
        for (int i = 0; i < k; ++i)
        {
            // 单次操作：记录并弹出最大值，修改后重新添加进堆
            // v.front() 是堆顶元素，pop_heap 会将堆顶元素和 v.back() 进行
            // 交换，然后再进行向下调整算法，并没有将堆顶元素 pop 掉
            pop_heap(piles.begin(), piles.end()); 
            piles.back() -= piles.back() / 2; // 堆顶元素减半
            // 从 v.back() 元素的位置开始向上调整，重新形成堆
            push_heap(piles.begin(), piles.end());
        }
        return accumulate(piles.begin(), piles.end(), 0);
    }
};

// 2760. 最长奇偶子数组
class Solution5
{
public:
    int longestAlternatingSubarray(vector<int>& a, int threshold) 
    {
        int n = a.size(), ret = 0, i = 0;
        while(i < n)
        {
            if((a[i] % 2) || (a[i] > threshold))
                ++i;
            else
            {
                int i0 = i;
                i += 1;
                while(i < n && a[i] <= threshold && (a[i] % 2 != a[i - 1] %2)) ++i;
                ret = max(ret, i - i0);
            }
        }
        return ret;
    }
};

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 2326. 螺旋矩阵 IV
class Solution6
{
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) 
    {
        vector<vector<int>> ret(m, vector<int>(n, -1));
        int x = 0, y = 0;
        int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int i = 0;
        while(head)
        {
            ret[x][y] = head->val;
            head = head->next;
            int nx = x + dirs[i][0], ny = y + dirs[i][1];
            if(nx < 0 || ny < 0 || nx >= m || ny >= n || ret[nx][ny] != -1)
            {
                i = (i + 1) % 4;
                nx = x + dirs[i][0], ny = y + dirs[i][1];
            }
            x = nx, y = ny;
        }

        return ret;
    }
};